package top.humbleyuan.leet.datastructure.tree;


import org.junit.Test;
import top.humbleyuan.leet.Array;

import java.util.*;

/**
 * @Author HumbleYuan
 * @Date 2019/12/13 9:14
 * @Des 树的遍历
 */
public class Traverse {

    public static void main(String[] args) {

        TreeNode treeNode = new TreeNode(5);
        treeNode.formTree();
        mid_recursion(treeNode);
        System.out.println("Ts中序:" + midTs);

        pre_recursion(treeNode);
        System.out.println("Ts先序:" + preTs);

        pos_recursion(treeNode);
        System.out.println("Ts后序:" + posTs);

        System.out.println();

        mid_cys(treeNode);
        System.out.println("Tc中序:" + midTc);

        pre_cys(treeNode);
        System.out.println("Tc先序:" + preTc);

        pos_cys(treeNode);
        System.out.println("Tc后序:" + posTc);

        levelT(treeNode);

    }

    /**
     * 递归
     */
    private static String midTs = "";   // 中序串
    private static String preTs = "";   // 先序串
    private static String posTs = "";   // 后序串

    // 中序
    public static void mid_recursion(TreeNode t) {

        if(t == null) {
            return;
        }

        mid_recursion(t.left);
        midTs += t.val + " ";
        mid_recursion(t.right);
    }

    // 先序
    public static void pre_recursion(TreeNode t) {

        if(t == null) {
            return;
        }

        preTs += t.val + " ";
        pre_recursion(t.left);
        pre_recursion(t.right);
    }

    // 后序
    public static void pos_recursion(TreeNode t) {

        if(t == null) {
            return;
        }

        pos_recursion(t.left);
        pos_recursion(t.right);
        posTs += t.val + " ";
    }


    /**
     * 非递归
     */
    private static String midTc = "";   // 中序串
    private static String preTc = "";   // 先序串
    private static String posTc = "";   // 后序串

    // 中序
    public static void mid_cys(TreeNode t) {
        TreeNode temp = t;
        Stack<TreeNode> stack = new Stack<>();

        while (!stack.empty() || temp != null) {

            while(temp != null) {
                stack.push(temp);
                temp = temp.left;
            }

            temp = stack.pop();
            midTc += temp.val + " ";

            // 以此时tem为root找其右子树的最左孩子
            temp = temp.right;
        }
    }

    // 先序
    public static void pre_cys(TreeNode t) {
        TreeNode temp = t;
        Stack<TreeNode> stack = new Stack<>();

        while (!stack.empty() || temp != null) {

            while(temp != null) {
                stack.push(temp);
                preTc += temp.val + " ";
                temp = temp.left;
            }

            temp = stack.pop();

            // 以此时tem为root找其右子树的最左孩子
            temp = temp.right;
        }
    }

    // 后序
    public static void pos_cys(TreeNode t) {
        TreeNode temp = t;

        /**
         * 后序特殊，按照左右中遍历
         */
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> vals = new ArrayList<>();
        stack.push(temp);

        while (!stack.empty()) {
            TreeNode tem = stack.pop();
            vals.add(tem.val);

            /**
             * 这里注意先左后右压入，取出时顺序为中右左，最后做逆序
             */
            if(tem.left != null) {
                stack.push(tem.left);
            }

            if(tem.right != null) {
                stack.push(tem.right);
            }
        }

        for (int i = vals.size()-1; i >= 0; i--) {
            posTc += vals.get(i) + " ";
        }

    }

    /**
     * 层次遍历
     * 需要用到一个队列，按顺序存储遍历到的对象，先进先出
     * 因为队列中元素必定是按层次顺序加进去的，
     * 所以每次拿到队列中尾部元素并加入list即是层次遍历
     */
    public static void levelT(TreeNode t) {
        List<Integer> list = new ArrayList<>();
        if(t == null) {
            System.out.println(list);
            return;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(t);

        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            list.add(cur.val);

            if(cur.left != null) {
                queue.offer(cur.left);
            }

            if(cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }



}
